//050. 连续素数的和
//        素数 41 可以写成六个连续素数的和：
//        41=2+3+5+7+11+13
//        这是一百以下可以被写成连续素数的和中包含素数最多的。
//        一千以下可以被写成连续素数的和，并且包含素数最多的素数是 953，这个和中包含 21 个
//        素数。求一百万以下可以被写成包含最多的连续素数的和的素数。
//        答案：997651

//看了题解 T_T
//思路来源：https://pe.metaquant.org/pe050.html
public class Week050 {
    static int[] primes;
    static int[] mv;

    /*
     *@ prime[i] :第i+1个素数
     *@ mv[i]    :i的最小质因子
     *@ 质数的最小质因子为它本身
     *@ 请不要更改传入的数组的值（即全为0）
     */
    // 欧拉筛1~n的素数
    public static int getPrime(int[] prime, int[] mv, int n) {
        int tot = 0;
        for (int i = 2; i <= n; ++i) {
            if (mv[i] == 0) {
                prime[++tot] = i;
                mv[i] = i;
            }
            for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
                mv[i * prime[j]] = prime[j];
                if (i % prime[j] == 0) break;
            }
        }
        return tot;
    }

    static boolean isPrime(int x) {
        return mv[x] == x;
    }

    static void run() {
        final int n = 1000000;
        primes = new int[n + 1];
        mv = new int[n + 1];
        int cnt = getPrime(primes, mv, n);
        //前缀和数组primes [l,r]之间的和为 sum[r]-sum[l-1]
        int[] sum = new int[cnt + 1];
        for (int i = 1; i <= cnt; ++i) sum[i] = primes[i] + sum[i - 1];
        //找到刚好超过n的素数和个数
        int maxSize = 0;
        while (sum[maxSize] < n) ++maxSize;
        for (int i = maxSize; i > 0; --i) {
            for (int j = 1; j <= maxSize - i; ++j) {
                int ans = sum[j + i - 1] - sum[j - 1];
                if (isPrime(ans)) {
                    System.out.println(ans);
                    return;
                }
            }
        }
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
